// EMERGENT GAME TECHNOLOGIES PROPRIETARY INFORMATION
//
// This software is supplied under the terms of a license agreement or
// nondisclosure agreement with Emergent Game Technologies and may not 
// be copied or disclosed except in accordance with the terms of that 
// agreement.
//
//      Copyright (c) 1996-2008 Emergent Game Technologies.
//      All Rights Reserved.
//
// Emergent Game Technologies, Chapel Hill, North Carolina 27517
// http://www.emergent.net

#ifndef NITMAPBASE_H
#define NITMAPBASE_H

#include <GnRTLib.h>
#include <GnMemObject.h>
#include <GnUniversalTypes.h>

// The map class implements a hash table of TKEY to store values of TVAL.
// It uses modular arithmetic for building the hash keys with a default
// table size of 37.  If you want a larger table size, the best bet is to
// us a large prime number.  Consult a standard text on hashing for the
// basic theory.
//
// TKEY MUST BE THE SAME SIZE AS A POINTER!
//
// The template class assumes that type TKEY has the following:
//   1.  Default constructor, TKEY::TKEY();
//   2.  Copy constructor, TKEY::TKEY(const TKEY&);
//   3.  Assignment, TKEY& operator=(const TKEY&);
//   4.  Comparison, bool TKEY::operator==(const TKEY&), or supply a
//       specialized equality testing class in your template.
//   5.  Implicit conversion, TKEY::operator long(), for building hash key,
//       or you must pass in your own hash function class in your template.
//
// The template class assumes that type TVAL has the following:
//   1.  Default constructor, TVAL::TVAL();
//   2.  Copy constructor, TVAL::TVAL(const TVAL&);
//   3.  Assignment, TVAL& operator=(const TVAL&);
//
// In both cases, the compiler-generated default constructor, copy
// constructor, and assignment operator are acceptable.
//
// Example of iteration over map
//
//     GnTMap<TKEY,TVAL> kMap;
//     GnTMapIterator pos = kMap.GetFirstPos();
//     while (pos)
//     {
//         TKEY key;
//         TVAL val;
//         kMap.GetNext(pos,key,val);
//         <process key and val here>;
//     }

typedef void* GnTMapIterator;

// The GnTMapItem class used to be nested in GnTMap. It was made a separate
// class because having it nested caused g++ to hit an internal error.

template <class TKEY, class TVAL> class GnTMapItem : public GnMemObject
{
public:
    GnTMapItem* m_pkNext;
    TKEY m_key;
    TVAL m_val;
};

// The hash function class
template <class TKEY> class GnTMapHashFunctor : public GnMemObject
{
public:
    static unsigned int KeyToHashIndex(TKEY key, GnUInt32 uiTableSize);
};

// The equality function class
template <class TKEY> class GnTMapEqualsFunctor : public GnMemObject
{
public:
    static bool IsKeysEqual(TKEY key1, TKEY key2);
};

template <class TheAllocator, class TKEY, class TVAL,
    class THASH = GnTMapHashFunctor<TKEY>,
    class TEQUALS = GnTMapEqualsFunctor<TKEY> > class GnTMapBase :
    public GnMemObject
{
public:
    // construction and destruction
    GnTMapBase(GnUInt32 uiHashSize = 37);
    virtual ~GnTMapBase();

    // counting elements in map
    GnUInt32 GetCount() const;
    bool IsEmpty() const;

    // add or remove elements
    void SetAt(TKEY key, TVAL val);
    bool RemoveAt(TKEY key);
    void RemoveAll();

    // element access
    bool GetAt(TKEY key, TVAL& val) const;

    // map traversal
    GnTMapIterator GetFirstPos() const;
    void GetNext(GnTMapIterator& pos, TKEY& key, TVAL& val) const;
    
    /**
        Resize the map.
        
        The hash table of the map is resized to the given size (which must be
        non-zero), and all of the entries in the map are re-mapped to new
        locations. Any interators will be invalid after this operation. This
        operation is expensive for large maps - the cost is at least linear
        in the number of entries.
    */
    void Resize(GnUInt32 uiNewHashSize);

protected:
    // hash table stored as array of doubly-linked lists
    GnTMapItem<TKEY,TVAL>* GetPtrToAssoc(TKEY key) const;
    virtual void SetValue(GnTMapItem<TKEY,TVAL>* pkItem, TKEY key, TVAL val);
    virtual void ClearValue(GnTMapItem<TKEY,TVAL>* pkItem);
    
    virtual GnTMapItem<TKEY, TVAL>* NewItem() = 0;
    virtual void DeleteItem(GnTMapItem<TKEY, TVAL>* pkItem) = 0;
    
    GnUInt32 m_uiHashSize;             // maximum slots in hash table
    GnTMapItem<TKEY,TVAL>** m_ppkHashTable;// hash table storage

    struct AntiBloatAllocator : public TheAllocator
    {
        // We reduce TheAllocator by 4 bytes by deriving
        // See http://www.cantrip.org/emptyopt.html
        GnUInt32 m_uiCount;      // number of elements in list
    };

    AntiBloatAllocator m_kAllocator;  

private:
    // To prevent an application from inadvertently causing the compiler to
    // generate the default copy constructor or default assignment operator,
    // these methods are declared as private. They are not defined anywhere,
    // so code that attempts to use them will not link.
    GnTMapBase(const GnTMapBase&);
    GnTMapBase& operator=(const GnTMapBase&);
};

//---------------------------------------------------------------------------
// Inline include
#include "GnTMapBase.inl"
//---------------------------------------------------------------------------

#endif // NITMAPBASE_H
